Increasing the rate at which digital data can be processed is an important goal in almost every analog and digital design. One known structure for data processing is commonly referred to as a "pipeline". In a typical pipeline structure, data is received at a first processing station or stage and is passed in a predetermined order to subsequent stages in the pipeline. Each pipeline stage may either process the data or simply act as a conduit and pass it on during the next clock cycle of the pipeline.
Existing pipelines, however, are typically "rigid", so that a delay at in stage of the pipeline causes the entire pipeline to stop; the pipeline must wait until the busy stage has completed its task. Depending on the application, data could then either be lost or must be stored temporarily and later retrieved and processed even faster in order to "catch up". In any case, however, stopping the entire pipeline because of a delay in one stage reduces the processing speed and efficiency of the pipeline structure.
As one example, in systems involving the transfer of digital video data, a pipeline may be used to receive and process transmitted video data. In such image transmission systems, if data can be processed faster, than either that more channels of information can be transmitted and processed simultaneously using the same medium, or more data can be transmitted and processed for each image for a given period of time.
In digital television systems, such as the High-Definition TV (HDTV) that is expected to replace existing analog technology, the faster digital video data can be processed, the better the resolution one can obtain. As with photographs, the finer the grain, the more life-like the image will be. Similarly, the more picture elements ("pixels") a television screen contains, and the faster the screen image is updated, the more life-like the picture will appear.
In order to achieve high-speed transfer and processing of video data, however, the television set that receives the signals must obviously be able to receive and process the signals as fast as they are sent. Otherwise, assuming a steady stream of transmitted data, any temporary memory storage devices used in the receiver might eventually fill up and data would be lost since the storage devices must be of a size limited to a range on the order of tens of frames. Storage devices sufficient to store hundreds of frames are not practical or desirable in most video reception devices.
Temporary, high-speed storage of transmitted data for use at a lower processing rate in a receiving device is therefore only suitable for a known, limited amount of data, and data transmission must not be so fast that the storage device fills up before the receiver is finished processing the data it has already received and stored. In video applications such as television, however, "slow motion" processing by the receiver would obviously be unacceptable. The receiver should therefore be able to receive data no slower than the rate at which it is transmitted. If a rigid pipeline is used to process such digital video signals, a delay in any stage of the pipeline causes the entire pipeline to stop. In such case, transmission must halt, or transmitted data must be stored temporarily lest it be lost altogether.
Another drawback of existing data pipelines is that whenever one stage in the pipeline is delayed, corresponding control signals must be propagated all the way back through earlier stages to the initial pipeline stage in order to prevent further processing until the active stage has completed its task. This means that earlier stages in the pipeline are unnecessarily idle.
What is needed is a data pipeline structure that does not suffer from the disadvantages mentioned above, each of which causes existing pipeline structures to process data more slowly. In particular, an improved pipeline structure should have the following characteristics:
1. The pipeline should be "elastic" such that a slow-down at a following pipeline stage should not lock up preceding pipeline stages and prevent processing in other stages; PA1 2. It should not be necessary for signals to propagate back to the beginning of the pipeline when a later pipeline processing stage is not able to accept new data; PA1 3. A pipeline stage should not need to know in advance anything about the data that it is accepting; and PA1 4. No time should be spent before transferring data between pipeline stages in order to establish the parameters of the transfer.
It is the object of this invention to provide a pipeline structure for data processing that meets these needs.